1. Field of the Invention
The present invention relates to computer networks and more particularly to efficiently managing bandwidth (BW) registration for multiple spanning tree options in a computer network.
2. Background Information
Many organizations, including businesses, governments and educational institutions, utilize computer networks so that employees and others may share and exchange information and/or resources. A computer network typically comprises a plurality of entities interconnected by means of one or more communications media. An entity may consist of any device, such as a computer, that “sources” (i.e., transmits) or “sinks” (i.e., receives) data frames over the communications media. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, or a wireless protocol, that defines the functions performed by data link and physical layers of a communications architecture (i.e., a protocol stack).
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a “switching” function between two or more LANs or end stations. Typically, the bridge is a computer and includes a plurality of ports that are coupled via LANs either to other bridges, or to end stations such as routers or host computers. Ports used to couple bridges to each other are generally referred to as a trunk ports, whereas ports used to couple bridges to end stations are generally referred to as access ports. The bridging function includes receiving data from a sending entity at a source port and transferring that data to at least one destination port for forwarding to one or more receiving entities.
Spanning Tree Algorithm
Most computer networks include redundant communications paths so that a failure of any given link does not isolate any portion of the network. Such networks are typically referred to as meshed or partially meshed networks. The existence of redundant links, however, may cause the formation of circuitous paths or “loops” within the network. Loops are highly undesirable because data frames may traverse the loops indefinitely.
Furthermore, some devices, such as bridges or switches, replicate frames whose destination is not known resulting in a proliferation of data frames along loops. The resulting traffic can overwhelm the network. Other intermediate devices, such as routers, that operate at higher layers within the protocol stack, such as the Internetwork Layer of the Transmission Control Protocol/Internet Protocol (“TCP/IP”) reference model, deliver data frames and learn the addresses of entities on the network differently than most bridges or switches, such that routers are generally not susceptible to sustained looping problems.
To avoid the formation of loops, most bridges and switches execute a spanning tree protocol which allows them to calculate an active network topology that is loop-free (i.e., a tree) and yet connects every pair of LANs within the network (i.e., the tree is spanning). The IEEE promulgated a standard (IEEE Std. 802.1D-1998™) that defines a spanning tree protocol to be executed by 802.1D compatible devices. In general, by executing the 802.1D spanning tree protocol, bridges elect a single bridge within the bridged network to be the “Root Bridge”. The 802.1D standard takes advantage of the fact that each bridge has a unique numerical identifier (bridge ID) by specifying that the Root Bridge is the bridge with the lowest bridge ID. In addition, for each LAN coupled to any bridge, exactly one port (the “Designated Port”) on one bridge (the “Designated Bridge”) is elected. The Designated Bridge is typically the one closest to the Root Bridge. All ports on the Root Bridge are Designated Ports, and the Root Bridge is the Designated Bridge on all the LANs to which it has ports.
Each non-Root Bridge also selects one port from among its non-Designated Ports (its “Root Port”) which gives the lowest cost path to the Root Bridge. The Root Ports and Designated Ports are selected for inclusion in the active topology and are placed in a forwarding state so that data frames may be forwarded to and from these ports and thus onto the LANs interconnecting the bridges and end stations of the network. Ports not included within the active topology are placed in a blocking state. When a port is in the blocking state, data frames will not be forwarded to or received from the port. A network administrator may also exclude a port from the spanning tree by placing it in a disabled state.
To obtain the information necessary to run the spanning tree protocol, bridges exchange special messages called configuration bridge protocol data unit (BPDU) messages or simply BPDUs. BPDUs carry information, such as assumed root and lowest root path cost, used in computing the active topology. More specifically, upon start-up, each bridge initially assumes itself to be the Root Bridge and transmits BPDUs accordingly. Upon receipt of a BPDU from a neighboring device, its contents are examined and compared with similar information (e.g., assumed root and lowest root path cost) stored by the receiving bridge in memory. If the information from the received BPDU is “better” than the stored information, the bridge adopts the better information and uses it in the BPDUs that it sends (adding the cost associated with the receiving port to the root path cost) from its ports, other than the port on which the “better” information was received. Although BPDUs are not forwarded by bridges, the identifier of the Root Bridge is eventually propagated to and adopted by all bridges as described above, allowing them to select their Root Port and any Designated Port(s).
In order to adapt the active topology to changes and failures, the Root Bridge periodically (e.g., every hello time) transmits BPDUs. In response to receiving BPDUs on their Root Ports, bridges transmit their own BPDUs from their Designated Ports, if any. Thus, BPDUs are periodically propagated throughout the bridged network, confirming the active topology. As BPDU information is updated and/or timed-out and the active topology is re-calculated, ports may transition from the blocking state to the forwarding state and vice versa. That is, as a result of new BPDU information, a previously blocked port may learn that it should be in the forwarding state (e.g., it is now the Root Port or a Designated Port).
Virtual Local Area Networks
A computer network may also be segmented into a series of logical networks. For example, U.S. Pat. No. 5,394,402, issued Feb. 28, 1995 to Ross (the “'402 patent”), discloses an arrangement for associating any port of a switch with any particular network segment. Specifically, according to the '402 patent, any number of physical ports of a particular switch may be associated with any number of groups within the switch by using a virtual local area network (VLAN) arrangement that virtually associates the port with a particular VLAN designation. More specifically, the switch or hub associates VLAN designations with its ports and further associates those VLAN designations with messages transmitted from any of the ports to which the VLAN designation has been assigned.
The VLAN designation for each port is stored in a memory portion of the switch such that every time a message is received on a given access port the VLAN designation for that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in the memory portion based on the particular access port at which the message was received. In many cases, it may be desirable to interconnect a plurality of these switches in order to extend the VLAN associations of ports in the network. Those entities having the same VLAN designation function as if they are all part of the same LAN. VLAN-configured bridges are specifically configured to prevent message exchanges between parts of the network having different VLAN designations in order to preserve the boundaries of each VLAN. Nonetheless, intermediate network devices operating above L2, such as routers, can relay messages between different VLAN segments.
In addition to the '402 patent, the IEEE promulgated the 802.1Q specification standard for Virtual Bridged Local Area Networks. To preserve VLAN associations of messages transported across trunks or links in VLAN-aware networks, both Ross and the IEEE Std. 802.1Q-2005 specification standard disclose appending a VLAN identifier (VID) field to the corresponding frames. In addition, U.S. Pat. No. 5,742,604 to Edsall et al. (the “'604 patent”), which is commonly owned with the present application, discloses an Interswitch Link (ISL) encapsulation mechanism for efficiently transporting packets or frames, including VLAN-modified frames, between switches while maintaining the VLAN association of the frames. In particular, an ISL link, which may utilize the Fast Ethernet standard, connects ISL interface circuitry disposed at each switch. The transmitting ISL circuitry encapsulates the frame being transported within an ISL header and ISL error detection information, while the ISL receiving circuitry strips off this information and recovers the original frame.
Multiple Spanning Tree Protocol
Within the IEEE Std. 802.1Q-2005, the IEEE also included a specification standard for a Spanning Tree Protocol that is specifically designed for use with networks that support VLANs. The Multiple Spanning Tree Protocol (MSTP), which is described in the IEEE Std. 802.1Q-2005, organizes a bridged network into regions. Within each region, MSTP establishes an Internal Spanning Tree (IST) which provides connectivity to all bridges within the respective region and to the ISTs established within other regions. The IST established within each MSTP Region also provides connectivity to the one Common Spanning Tree (CST) established outside of the MSTP regions by IEEE Std. 802.1Q-2005 compatible bridges running STP or RSTP. The IST of a given MST Region receives and sends BPDUs to the CST. Accordingly, all bridges of the bridged network are connected by a single Common and Internal Spanning Tree (CIST). From the point of view of the legacy or IEEE Std. 802.1Q-2005 bridges, moreover, each MST Region appears as a single virtual bridge on the CST.
Within each MST Region, the MSTP compatible bridges establish a plurality of active topologies, each of which is called a Multiple Spanning Tree Instance (MSTI). The MSTP bridges also assign or map each VLAN to one and only one of the MSTIs. Because VLANs may be assigned to different MSTIs, frames associated with different VLANs can take different paths through an MSTP Region. The bridges may, but typically do not, compute a separate topology for every single VLAN, thereby conserving processor and memory resources. Each MSTI is basically a simple RSTP instance that exists only inside the respective Region, and the MSTIs do not interact outside of the Region.
MSTP, like the other spanning tree protocols, uses BPDUs to establish the ISTs and MSTIs as well as to define the boundaries of the different MSTP Regions. The bridges do not send separate BPDUs for each MSTI. Instead, every MSTP BPDU carries the information needed to compute the active topology for all of the MSTIs defined within the respective Region. Each MSTI, moreover, has a corresponding Identifier (ID) and the MSTI IDs are encoded into the bridge IDs. That is, each bridge has a unique ID, as described above, and this ID is made up of a fixed portion and a settable portion. With MSTP, the settable portion of a bridge's ID is further organized to include both a settable priority component and a system ID extension. The system ID extension corresponds to the CIST or one of the MSTI IDs. The MSTP compatible bridges within a given Region will thus have a different bridge ID for the CIST and each MSTI. For a given MSTI, the bridge having the lowest bridge ID for that instance is elected the root. Thus, an MSTP compatible bridge may be the root for one MSTI but not another within a given MSTP Region.
Each bridge running MSTP also has a single MST Configuration Identifier (ID) that consists of three attributes: an alphanumeric configuration name, a revision level and a VLAN mapping table that associates each of the potential 4096 VLANs to a corresponding MSTI. Each bridge, moreover loads its MST Configuration ID into the BPDUs sourced by the bridge. Because bridges only need to know whether or not they are in the same MST Region, they do not propagate the actual VLAN to MSTI tables in their BPDUs. Instead, the MST BPDUs carry only a digest of the VLAN to MSTI table or mappings. The digest is generated by applying the well-known MD-5 algorithm to the VLAN to MSTI table. When a bridge receives an MST BPDU, it extracts the MST Configuration ID contained therein, including the digest, and compares it with its own MST Configuration ID to determine whether it is in the same MST Region as the bridge that sent the MST BPDU. If the two MST Configuration IDs are the same, then the two bridges are in the same MST Region. If, however, the two MST Configuration IDs have at least one non-matching attribute, i.e., either different configuration names, different revision levels and/or different computed digests, then the bridge that received the BPDU concludes that it is in a different MST Region than the bridge that sourced the BPDU. A port of an MST bridge, moreover, is considered to be at the boundary of an MST Region if the Designated Bridge is in a different MST Region or if the port receives legacy BPDUs.
Registration Protocols
IEEE Std. 802.1p (now incorporated within IEEE 802.1D-2004) outlines the implementation of the Generic Attribute Registration Protocol (GARP) and related GARP applications which allow end stations and bridges to exchange membership information in a generic manner. In particular, GARP, as defined by IEEE 802.1p, “provides a generic attribute dissemination capability that is used by participants in GARP Applications (GARP Participants) to register and de-register attribute values with other GARP Participants within a Bridged LAN.” One application of GARP defined in IEEE 802.1p is the GARP Multicast Registration Protocol (GMRP), which allows GARP participants to join and leave multicast MAC (Media Access Control) address groups. The participant (e.g., an end station) who wishes to join a particular group registers with another GARP participant (e.g., a bridge) that is accepting registrations. This GARP participant (bridge) then applies for membership on behalf of the original participant (end station), which is propagated throughout the network. The information propagated by GMRP generally comprises the multicast MAC address. Another GARP application defined in IEEE 802.1p is the GARP VLAN Registration Protocol (GVRP). GVRP allows a participant to join and leave particular VLANs in a similar manner as GMRP, but involving VLAN membership information, e.g., VLAN IDs (VIDs), as defined in IEEE 802.1Q.
Generally, a GARP participant is responsible for handling GARP state machines and BPDU distribution. A participant in a multiport device (e.g., bridge/switch) that receives a registration for a particular attribute on a port declares (advertises) the attribute through the applicants on all of the other ports participating in GARP. The mechanism for propagating this information from one GARP participant to another within the same device is called GARP Information Propagation (GIP). A GIP context refers to the group of GARP participants belonging to a GIP. For each GIP context, there exists one GARP participant for each GARP application that is enabled on that port (e.g., one participant for each VLAN on that port in GMRP, and one participant for each port in GVRP). Each GARP participant may have both application-specific behavior and the GARP Information Declaration (GID) component, which may comprise, inter alia, one or more attribute values. An attribute is the application-specific information that is being propagated by GARP; e.g., a group MAC addresses and service requirements for GMRP, VIDs for GVRP, etc.
Notably, in addition to the GARP application protocols, IEEE 802.1p also explains how to utilize a tagging scheme to allow frames to be tagged with priority information and an optional VID. The prioritization operates at the MAC layer of the traffic, and classifies (groups) traffic into separate traffic classes. Eight classes are defined by IEEE 802.1p, which are to be configured manually by network administrators (the IEEE has made broad recommendations), and registered throughout the network. Illustratively, the highest priority is seven, which, for example, may be assigned to network-critical traffic, such as Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) updates. Values five and six may be used for delay-sensitive applications such as interactive video and voice, while data classes four through one range from controlled-load applications such as streaming multimedia and business-critical traffic down to “loss eligible” traffic. The zero value is used as a best-effort default, which may be invoked automatically when no other value has been set.
A new IEEE project, P802.1ak (Draft 5.1), identifies the Multiple Registration Protocol (MRP) standard for use with registrations (officially entitled the “Standard for Local and Metropolitan Area Networks Virtual Bridged Local Area Networks—Amendment 07: Multiple Registration Protocol”). MRP, an update (or replacement) to GARP, allows participants in an MRP Application to register attributes with other participants in a bridged LAN. A Multiple VLAN Registration Protocol (MVRP) is defined within IEEE P802.1ak to communicate topology changes for each VLAN independently of the spanning tree supporting the VLAN (e.g., an update to GVRP). This allows multiple VLANs to use a single spanning tree without requiring a bridge to relearn addresses for a given VLAN when a topology change does not change the bridge ports used to reach end stations receiving frames for that VLAN, as will also be understood by those skilled in the art. A Multiple Multicast Registration Protocol (MMRP) is also defined that updates GMRP in a similar manner. Those skilled in the art will understand that the MRP update allows for reduced fault recovery time (convergence time) and reduced disruption of traffic in a very large network due to a topology change in a small portion of that network.
Service Bandwidth Considerations
Customers (users) often desire to send traffic across a provider network (e.g., a bridged network) to other customers. The traffic or data “flows” enter the provider network from a source customer, e.g., at a User-Customer Interface (UNI) of an “entry bridge,” and traverse nodes (e.g., bridges) of the provider network to reach the destination customer of the flow, e.g., at a remote UNI (and “exit bridge”). Notably, if one provider network is attached to another provider network, the networks may be attached by Network Node Interfaces (NNIs). These customer-to-customer or “point-to-point” (P2P) transmissions (services) may require the use of a certain amount of bandwidth (BW) to transmit the data. “Multipoint-to-Multipoint” (MP2MP) services, on the other hand, are services in which any number of multiple points (e.g., customers) can transmit and receive data flows across the network to/from any number of other multiple points (i.e., more than two UNIs).
In some instances, it is desirable to guarantee or reserve the BW required for the transmission along the path of the data flow between points (a “conversation”), e.g., according to a particular spanning tree, to ensure that the traffic flowing between the points has enough BW. Otherwise, traffic may be dropped or suspended due to excess traffic along the path, e.g., due to other flows or conversations. For example, “Audio Visual Bridging” (AVB) is used to describe the technology associated with connecting video and audio components, e.g., set-top boxes, radios, etc., to a bridged network (e.g., an Ethernet). The data flows in AVB (or “streams”) may require a certain quality of service (QoS) to operate effectively, such as requiring a certain amount of BW for the stream, as well as requirements for latency, jitter, etc. Applications running the AVB services may request that the BW be reserved (registered) across the network (i.e., from the source to the destination) for the particular services, so that the transmission is guaranteed to be functional (i.e., has enough BW).
The use of spanning trees, as described above and as will be understood by those skilled in the art, has many useful applications. However, many customer devices (e.g., executing AVB services) often have multiple connections to the network. For example, redundant connections may interconnect a single device to the network, multiple application instances (e.g., one for audio, one for video, one for data, etc.) may be located on a single customer device, etc. By using a single spanning tree to connect the source customer to one or more destination customers, there is only one path between each end point. As such, all data flows from the source customer utilize the single spanning tree path, which may cause critical links to become saturated with traffic. This, in turn, may increase the difficulty of meeting the BW requirements of the services, as well as limit the number or quality of application services that may be used by the customers.
Spanning trees can be created by methods other than those described in IEEE Std. 802.1D-2004 or 802.1Q-2005. Those skilled in the art commonly recognize two principle classes of algorithms used to compute the paths over which data packets are to be forwarded: link state algorithms, and distance vector algorithms. Example link state algorithms include, e.g., the Open Shortest Path First (OSPF) protocol, described in Request for Comment (RFC) 2328, entitled OSPF Version 2, dated April 1998, and the Intermediate-System-to-Intermediate-System (IS-IS) protocol, described in RFC 1195, entitled Use of OSI IS-IS for routing in TCP/IP and Dual Environments, dated December 1990, both of which are hereby incorporated by reference. Also, example distance vector algorithms include, e.g., the Routing Information Protocol (RIP), described in RFC 1723, entitled RIP Version 2, dated November 1994, and MSTP (IEEE Std. 802.1Q-2005). As described in the above-incorporated commonly-owned copending U.S. application Ser. No. 11/182,564, entitled METHODS AND DEVICES FOR IMPROVING THE MULTIPLE SPANNING TREE PROTOCOL, and Ser. No. 11/228,162, entitled SYSTEM AND METHOD FOR GENERATING SYMMETRICAL SPANNING TREES, the spanning trees commonly computed using MSTP can also be computed using link state algorithms. As used herein, this technique is referred to as “Optimal Bridging.”
In both classes of algorithms, bridges transmit and receive information among each other in update packets (or BPDUs) in order to create the spanning trees. Unlike the distance vector algorithms, the link state algorithms supply each bridge with the information needed for that bridge to compute a model of the current topology of the network, including every bridge and every LAN.
In many cases, the network connecting the source and destination end points may have multiple paths between them, e.g., possibly connected to the multiple connections of the customer devices. However, even where some of those multiple paths have available resources (e.g., BW), they are generally unavailable to the customers because of the single spanning tree configuration. What this means, then, is that if the single spanning tree used by an entry bridge for a customer device has no available resources, the customer device is unable to satisfy its QoS requirements (e.g., BW), regardless of whether another path exists over the network to the destination(s).
There remains a need, therefore, for a technique that efficiently manages BW registration for the multiple paths across the network. In particular, a need exists for bridges of the network to optimally utilize available resources of the network, regardless of whether the available resources are on the single (primary) spanning tree used by the bridge. At the same time, however, conventional spanning tree techniques should be maintained in order to achieve the benefits of spanning trees (e.g., loop-free environments, etc.)